import java.util.Arrays;

/**
 * 归并排序：基于递归比较，使用额外空间的 O(nlogN) 的排序算法
 * TODO 出错了， 还需要思考， 练习
 */
public class MergeSort {

    private MergeSort() {
    }

    // 归并
    public static <E extends Comparable<E>> void sort(E[] data) {
        sort(data, 0, data.length - 1);
    }

    private static <E extends Comparable<E>> void sort(E[] data, int l, int r) {
        if (l >= r) return;
//        if (r - l < 15) {
//            InsertionSort.sortV3(data, l, r + 1); // TODO 优化二：插入排序，减少内存分配次数，这里有问题
//            return;
//        }

        int mid = l + (r - l) / 2;
        sort(data, l, mid);   // 拆分
        sort(data, mid + 1, r); // 拆分
        if (data[mid].compareTo(data[mid + 1]) > 0) // 优化一：必要时进行归并， 减少扫描次数
            merge(data, l, mid, r); // 归并
    }

    // TODO
    // 要点： merge 过程，如何合并两个有序数组
    private static <E extends Comparable<E>> void merge(E[] data, int l, int mid, int r) {
        E[] copied = Arrays.copyOfRange(data, l, r + 1);
        int i = l;
        int j = mid + 1;
        for (int k = l; k <= r; k++) {
            if(i > mid) {
                data[k] = copied[j - l]; j++;
            }else if (j > r){
                data[k] = copied[i - l]; i++;
            }else if (copied[i - l].compareTo(copied[j - l]) <= 0) {
                data[k] = copied[i - l]; i++;
            }else {
                data[k] = copied[j - l]; j++;
            }
        }
    }
}
